A comparison of mixed integer programming formulations of the capacitated lot-sizing problem

We propose a novel mixed integer programming formulation for the capacitated lot-sizing problem with set-up times and set-up carryover. We compare our formulation to two earlier formulations, the Classical and Modified formulations, and a more recent formulation due to Suerie and Stadtler. Extensive computational experiments show that our formulation consistently outperforms the Classical and Modified formulations in terms of CPU time and solution quality. It is competitive with the Suerie–Stadtler (S&S) formulation, but outperforms all other formulations on the most challenging instances, those with low-capacity slack and a dense jobs matrix. We show that some of the differences in the performance of these various formulations arise from their different use of binary variables to represent production or set-up states. We also show that the LP relaxation of our Novel formulation provides a tighter lower bound than that of the Modified formulation. Our experiments demonstrate that, while the S&S formulation provides a much tighter LP bound, the Novel formulation is better able to exploit the intelligence of the CPLEX solution engine.     

A Pareto biogeography-based optimisation for multi-objective two-sided assembly line sequencing problems with a learning effect

This research presents a Pareto biogeography-based optimisation (BBO) approach to mixed-model sequencing problems on a two-sided assembly line where a learning effect is also taken into consideration. Three objectives which typically conflict with each other are optimised simultaneously comprising minimising the variance of production rate, minimising the total utility work and minimising the total sequence-dependent setup time. In order to enhance the exploration and exploitation capabilities of the algorithm, an adaptive mechanism is embedded into the structure of the original BBO, called the adaptive BBO algorithm (A-BBO). A-BBO monitors a progressive convergence metric in every certain generation and then based on this data it will decide whether to adjust its adaptive parameters to be used in the next certain generations or not. The results demonstrate that A-BBO outperforms all comparative algorithms in terms of solution quality with indifferent solution diversification.     

Interactive minimax optimisation for integrated performance analysis and resource planning

Analysing performances for future improvement and resource planning is a key management function. Data Envelopment Analysis (DEA) provides an analytical mean for performance modelling without assuming parametric functions. Multiple Objective Optimisation (MOO) is well-suited for resource planning. This paper reports an investigation in exploring relationships between DEA and MOO models for equivalent efficiency analysis in a MOO process. It is shown that under certain conditions minimax reference point models are identical to input-oriented dual DEA models for performance assessment. The former can thus be used for Hybrid Efficiency and Trade-off Analyses (HETA). In this paper, these conditions are first established and the equivalent models are explored both analytically and graphically to better understand HETA. Further investigation in the equivalence models leads to the modification of efficiency measures and the development of a minimax reference point approach for supporting integrated performance analysis and resource planning, with the Decision Maker’s (DM) preferences taken into account in an interactive fashion. Both numerical and case studies are conducted to demonstrate the proposed approach and its potential applications.     

On finding representative non-dominated points for bi-objective integer network flow problems

This paper proposes a new algorithm to find a representation of the set of all non-dominated points of the bi-objective integer network flow problem. The algorithm solves a sequence of ε-constraint problems with a branch-and-bound algorithm to find a subset of non-dominated points that represents the set of all non-dominated points well in the sense of coverage or uniformity. At each iteration of the algorithm, one non-dominated point, determined by solving one ε-constraint problem, is added to the representation until it is guaranteed that the representation has the desired quality. Computational experiments on different problem types show the efficacy of the algorithm.     

Chaotic swarming of particles: A new method for size optimization of truss structures

A new combination of swarm intelligence and chaos theory is presented for optimal design of truss structures. Here the tendency to form swarms appearing in many different organisms and chaos theory has been the source of inspiration, and the algorithm is called chaotic swarming of particles (CSP). This method is a kind of multi-phase optimization technique which employs chaos theory in two phases, in the first phase it controls the parameter values of the particle swarm optimization (CPVPSO) and the second phase is utilized for local search (CLSPSO). Some truss structures are optimized using the CSP algorithm, and the results are compared to those of the other meta-heuristic algorithms showing the effectiveness of the new method.     

Asynchronous optimisation with the use of a cascade search algorithm

This paper introduces the development of an asynchronous approach coupled with a cascade optimisation algorithm. The approach incorporates concepts of asynchronous Markov processes and introduces a search process that is benefiting from distributed computing infrastructures. The algorithm uses concepts of partitions and pools to store intermediate solutions and corresponding objectives. Population inflections are performed periodically to ensure that Markov processes, still independent and asynchronous, make arbitrary use of intermediate solutions. Tested against complex optimisation problems and in comparison with commonly used Tabu Search, the asynchronous cascade algorithm demonstrates a significant potential in distributed operations with favourable comparisons drawn against synchronous and quasi-asynchronous versions of conventional algorithms.     

Tidal turbine array optimisation using the adjoint approach

Oceanic tides have the potential to yield a vast amount of renewable energy. Tidal stream generators are one of the key technologies for extracting and harnessing this potential. In order to extract an economically useful amount of power, hundreds of tidal turbines must typically be deployed in an array. This naturally leads to the question of how these turbines should be configured to extract the maximum possible power: the positioning and the individual tuning of the turbines could significantly influence the extracted power, and hence is of major economic interest. However, manual optimisation is difficult due to legal site constraints, nonlinear interactions of the turbine wakes, and the cubic dependence of the power on the flow speed. The novel contribution of this paper is the formulation of this problem as an optimisation problem constrained by a physical model, which is then solved using an efficient gradient-based optimisation algorithm. In each optimisation iteration, a two-dimensional finite element shallow water model predicts the flow and the performance of the current array configuration. The gradient of the power extracted with respect to the turbine positions and their tuning parameters is then computed in a fraction of the time taken for a flow solution by solving the associated adjoint equations. These equations propagate causality backwards through the computation, from the power extracted back to the turbine positions and the tuning parameters. This yields the gradient at a cost almost independent of the number of turbines, which is crucial for any practical application. The utility of the approach is demonstrated by optimising turbine arrays in four idealised scenarios and a more realistic case with up to 256 turbines in the Inner Sound of the Pentland Firth, Scotland.     

Managing information and supplies inventory operations in a manufacturing environment. Part 2: An order-timing and sizing algorithm

We develop a new, flexible independent demand forecasting-optimisation algorithm, and apply it to nine difficult-to-manage maintenance and repair products at the AREVA nuclear fuel rod manufacturing facility. The algorithm results in a 27% reduction in inventory holding and ordering costs relative to AREVA's baseline ERP method. This is in addition to improving the line item fill rates from 96 to 98%. This new algorithm is more flexible than the baseline method in that (1) our forecast error distribution is not assumed to be normal—we automatically find the best-fitting distribution from a large family of distributions, (2) we jointly optimise the order quantity and reorder point by using an optimisation routine that is embedded in a simulation methodology. Our algorithm can therefore handle a non-stationary demand process during the planning horizon, and (3) we dynamically select the best time series forecaster for demand based on the most recent history. This flexibility drove the performance improvements. Our algorithm can be easily adapted to any independent demand situation across any industry's supply chain.     

Cycle time-oriented mid-term production planning for semiconductor wafer fabrication

Wafers are produced in an environment with uncertain demand and failure-prone machines. Production planners have to react to changes of both machine availability and target output, and revise plans appropriately. The scientific community mostly proposes WIP-oriented mid-term production planning to solve this problem. In such approaches, production is planned by defining targets for throughput rates and buffer levels of selected operations. In industrial practice, however, cycle time-oriented planning is often preferred over WIP-oriented planning. We therefore propose a new linear programming formulation, which facilitates cycle time-oriented mid-term production planning in wafer fabrication. This approach plans production by defining release quantities and target cycle times up to selected operations. It allows a seamless integration with the subordinate scheduling level. Here, least slack first scheduling translates target cycle times into lot priorities. We evaluate our new methodology in a comprehensive simulation study. The results suggest that cycle time-oriented mid-term production planning can both increase service level and reduce cycle time compared to WIP-oriented planning. Further, it requires less modelling effort and generates plans, which are easier to comprehend by human planners.     

Adjustable Robust Optimisation approach to optimise discounts for multi-period supply chain coordination under demand uncertainty

In this research, a problem of supply chain coordination with discounts under demand uncertainty is studied. To solve the problem, an Affinely Adjustable Robust Optimisation model is developed. At the time when decisions about order periods, ordering quantities and discounts to offer are made, only a forecasted value of demand is available to a decision-maker. The proposed model produces a discount schedule, which is robust against the demand uncertainty. The model is also able to utilise the information about the realised demand from the previous periods in order to make decisions for future stages in an adjustable way. We consider both box and budget uncertainty sets. Computational results show the necessity of accounting for uncertainty, as the total costs of the nominal solution increase significantly even when only a small percentage of uncertainty is in place. It is testified that the affinely adjustable model produces solutions, which perform significantly better than the nominal solutions, not only on average, but also in the worst case. The trade-off between reduction of the conservatism of the model and the uncertainty protection is investigated as well.